上篇文章里面，我们已经学习了二叉搜索树的相关内容，二叉搜索树有一个缺点，在插入数据是有序的序列（包括升序和降序），会导致二叉树退化成链表，从而导致在查找，删除，添加时的性能均从O（logN）降低为O（N），这是不能接受的。如下图：

究其原因，是因为二叉搜索树退化成链表的时候，树的高度与节点的个数相等，也就是成正比，所以为了优化这种情况，就出现了具有平衡能力的二叉搜索树，其中AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O（logN）。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

平衡二叉树本质上是特殊的二叉搜索树（二叉排序树），它具有二叉搜索树所有的特点，此外它有自己的特别的性质，如下：

（1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1；

（2）平衡二叉树的左右两个子树都是一棵平衡二叉树。

平衡因子指的是，平衡二叉树在保持平衡的时候，是通过平衡因子来判断的，节点的平衡因子 = 该节点的左子树的高度 - 该节点右子树的高度。只有当值等于-1（右子树的高度大），0（左右子树的高度相等），1（左子树的高度大）的时候，能够代表该子树是平衡的除此之外，就认为该节点已经失衡了，需要旋转来维持平衡，如下图的平衡因子分布情况：

平衡二叉树在插入和删除的时候都有可能发生旋转来维持平衡，总得来说，旋转分四种情形：

（1）左旋转

如下图，对二叉搜索树分别插入1,2,3升序序列，会导致树向右倾斜，这个我们需要左旋来平衡树：

第一张图标记了，当插入3之后，根节点1失衡了，因为1节点没有左子树，所以左子树的高度等于0，而右子树的高度等于2，故两者相减得到-2，证明树失衡了，通过向左旋转，调整了root的位置，从而使得树变得均衡了。

（2）右旋转

如下图，对二叉搜索树分别插入3,2,1降序序列，会导致树向左倾斜，这种情况下我们需要向右旋转来平衡树：

在插入1后，树发现失衡了，故而通过向右旋转的方式，来调整平衡。

（3）左右旋转

如下图与（2）的情况类似，但不同的是插入的方式是3,1,2，从而导致最后一个2插入的时候，是在右子树上导致失衡的，这种情况下比前面的稍微复杂，需要旋转两次来调整平衡。

先左旋之后，发现仍然失衡，然后接着右旋才维持平衡。

（4）右左旋转

如下图，对二叉搜索树分别插入1,3,2，与上面的（3）情形正好相反

这种情况下，先右旋然后左旋就可以保持平衡

平衡二叉树的代码，其实和二叉搜索树的代码大体一致，包括搜索，插入和删除功能，主要的区别在于在树节点定义上多加了一个height字段，用来计算均衡因子使用，此外在插入和删除之后要加上检测平衡的代码，如果发现树失衡了就要及时调整：